class Solution {
  public:

    int m, n;
    vector<vector<bool>>vis;
    string str;
    int count = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    bool dfs(vector<string>& board, int x, int y, int count) {
        if (board[x][y] != str[count]) return false;
        if (count == str.size() - 1) return true;


        vis[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int i = x + dx[k];
            int j = y + dy[k];
            if (i >= 0 && i < m && j >= 0 && j < n && !vis[i][j] &&
                    dfs(board, i, j, count + 1)) {

                return true;
            }
        }

        vis[x][y] = false;
        return false;
    }
    bool exist(vector<string>& board, string word) {
        m = board.size(), n = board[0].size();
        str = word;
        vis = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (dfs(board, i, j, 0)) return true;
            }
        }
        return false;
    }

};



//将count作为全局变量来传递
class Solution {
  public:

    int m, n;
    vector<vector<bool>>vis;
    string str;
    int count = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    bool dfs(vector<string>& board, int x, int y) {
        if (board[x][y] != str[count]) return false;
        if (count == str.size() - 1) return true;

        count++;
        vis[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int i = x + dx[k];
            int j = y + dy[k];
            if (i >= 0 && i < m && j >= 0 && j < n && !vis[i][j] && dfs(board, i, j)) {
                
                return true;
            }
        }
        count--;
        vis[x][y] = false;
        return false;
    }
    bool exist(vector<string>& board, string word) {
        m = board.size(), n = board[0].size();
        str = word;
        vis = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                count=0;
                if (dfs(board, i, j)) return true;
            }
        }
        return false;
    }

};